package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/07/07
 */
public class 第405场单周赛 {

    public static void main(String[] args) {

        第405场单周赛 impl = new 第405场单周赛();

        //[[".",".","."],
        // ["Y",".","Y"],
        // [".",".","."],
        // [".","Y","X"]]
//        System.out.println(impl.numberOfSubmatrices(new char[][]{
//                {'X', 'Y', '.'},
//                {'Y', '.', '.'}
//        }));
        System.out.println(impl.numberOfSubmatrices(new char[][]{
                {'.', '.', '.'},
                {'Y', '.', 'Y'},
                {'.', '.', '.'},
                {'.', 'Y', 'X'}
        }));

    }

    /**
     * 模拟
     */
    public String getEncryptedString(String s, int k) {

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {

            stringBuilder.append(
                    s.charAt((i + k) % s.length())
            );

        }

        return stringBuilder.toString();
    }


    /**
     * 长度为 2 的字符串，可以由长度为 1 的字符串得到，以此类推
     * 注意长度 > 2 的字符串，连续2位子串是 01 10 11 就行
     */
    public List<String> validStrings(int n) {
        List<String> list = new ArrayList<>();
        if (n == 1) {
            list.add("0");
            list.add("1");
            return list;
        }

        Set<String> curSet = new HashSet<>();
        curSet.add("1");
        for (int i = 1; i < n; i++) {
            Set<String> nextSet = new HashSet<>();

            for (String str : curSet) {
                nextSet.add(str + "1");
                nextSet.add("1" + str);

                if (str.charAt(str.length() - 1) == '1') {
                    nextSet.add(str + "0");
                }
                if (str.charAt(0) == '1') {
                    nextSet.add("0" + str);
                }
            }

            curSet = nextSet;
        }


        for (String str : curSet) {
            list.add(str);
        }
        return list;
    }

    /**
     * 从左到右，从上往下遍历，汇总 X 和 Y 的总数量
     */
    public int numberOfSubmatrices(char[][] grid) {
        int ans = 0;

        int[][] preRowSum = new int[grid.length + 1][2];

        for (int column = 0; column < grid[0].length; column++) {
            int[][] curRowsum = new int[grid.length + 1][2];

            int[][] rowSum = new int[grid.length + 1][2];
            for (int row = 0; row < grid.length; row++) {

                if (grid[row][column] == 'X') {
                    rowSum[row + 1][0] = rowSum[row][0] + 1;
                    rowSum[row + 1][1] = rowSum[row][1];
                } else if (grid[row][column] == 'Y') {
                    rowSum[row + 1][1] = rowSum[row][1] + 1;
                    rowSum[row + 1][0] = rowSum[row][0];
                } else {
                    rowSum[row + 1][1] = rowSum[row][1];
                    rowSum[row + 1][0] = rowSum[row][0];
                }
                int Y = rowSum[row + 1][1] + preRowSum[row + 1][1];
                int X = rowSum[row + 1][0] + preRowSum[row + 1][0];

                curRowsum[row + 1][0] = X;
                curRowsum[row + 1][1] = Y;
                if (X >= 1 && X == Y) {
                    ans++;
                }
            }
            preRowSum = curRowsum;
        }
        return ans;
    }

}
